package 单调栈;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * TODO
 *
 * @Description
 * @Author Lx
 * @Date 2024/7/28 20:02
 **/
public class 单调栈1_每日温度 {

    public int[] dailyTemperatures(int[] temperatures) {
        // 单调栈：维护一个下标的栈，降序的，
        //进栈条件:只要arr[i]比栈顶元素小
        //出栈条件：只要arr[i]比栈顶元素大，就出栈并且记录下state[栈内元素的下标]=i;
        int[] res = new int[temperatures.length];

        Deque<Integer> st =new LinkedList<>();
        for (int i = 0; i < temperatures.length; i++) {
            //出栈
            if(!st.isEmpty()&&temperatures[i]>temperatures[st.peek()]){
                while(!st.isEmpty() && temperatures[st.peek()]<temperatures[i]){
                    Integer index = st.pop();
                    res[index] = i-index;
                }
                st.push(i);
            }else{//为空，或者
            //进栈
                st.push(i);
            }
        }
        return res;
    }

    public int[] dailyTemperatures_carl(int[] temperatures) {

        int lens=temperatures.length;
        int []res=new int[lens];

        /**
         如果当前遍历的元素 大于栈顶元素，表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素，
         所以弹出 栈顶元素，并记录
         如果栈不空的话，还要考虑新的栈顶与当前元素的大小关系
         否则的话，可以直接入栈。
         注意，单调栈里 加入的元素是 下标。
         */
        Deque<Integer> stack=new LinkedList<>();
        stack.push(0);
        for(int i=1;i<lens;i++){

            if(temperatures[i]<=temperatures[stack.peek()]){
                stack.push(i);
            }else{
                while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
                    res[stack.peek()]=i-stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }

        return  res;
    }
    public static void main(String[] args) {

        int[] arr = {73,74,75,71,69,72,76,73};
        int[] res = new 单调栈1_每日温度().dailyTemperatures(arr);
        for (int i : res) {
            System.out.print(i+" ");
        }
    }
}
